前言

上一章節談了引線二元樹的緣由、規則，也就是因為當使用LinkedList去表示二元樹時，一定會浪費一些鏈結空間，而為了不要浪費，我們利用這些空間作為引線，去指向中序前繼者或中序後繼者。
此外，也先談了在設計引線二元樹時的資料結構，要回去複習上ㄧ章節，才有辦法進入本章，因為本章即將進入引線二元樹的各種操作。

引線二元樹之操作

尋找中序後繼者

Insuc(x){ // 搜尋某點x之中序後繼者
	temp = x->rchild; 
	if(x->rthread == false){
		while(temp->lthread == false){ // 往左下找到底
			temp = temp->lchild;
        }
    }
	return temp
}

當我們在做中序追蹤的時候，使採取 LDR 的順序下去進行，因此只要是某點的中序的後繼者，必往其右下走後，再找左子點到底

尋找中序前繼者

只要將左右對調即可！

簡化中序追蹤

Inorder(t) // 此 t 代表 headnode
{
	temp = t ;
	repeat
		temp = insuc(temp); // 找中序後繼者
		print(temp);
	until temp==t // headnode point to itself
}

插入 t node 到 s node 成為右子點

insertToRight(s,t){
    t->rthread = s->rthread;
    t->rchild = s->rchild
    t->lthread = true;
    t->lchild = s;
    s->rthread = false;
    s->rchild = t;
    if(t->rthread == false){  // 代表原先狀況 s 有右子點
        temp = insuc(t);
        temp->lchild = t;
    }
}